A variety of integrated circuits, including general-purpose data processors and digital signal processors (DSPs), perform multiplications. Two multiplication operands, known generally as the multiplier and the multiplicand, are typically provided to dedicated multiplier circuitry. The speed and complexity of the multiplier circuitry varies with the application. For example, a hardware multiplier using a modified Booth's algorithm is preferred for many high-speed applications. A serial multiplier, however, may be preferred for more cost-sensitive applications which do not require as high a level of performance.
The operands are usually expressed as signed values in two's complement form. In two's complement, a most-significant bit is a sign bit in which a zero represents a positive number and a one represents a negative number. A negative number is expressed in two's complement by complementing each bit of a corresponding positive number and adding one to the result.
However, the two's complement number system is asymmetrical, which may complicate the multiplier circuitry. An example with numbers expressed in 4-bit, two's complement form illustrates this asymmetry. While the maximum positive number, expressed in binary as 0111, has a value of positive seven, the maximum negative number, expressed in binary as 1000, has a value of negative eight. Thus, two's complement is able to express a maximum negative number having an absolute value of one greater than the maximum positive number. As used in the following discussion, the binary quantity "0111" has a most-significant or fourth bit of "0", and three least-significant bits or first, second, and third bits of "1".
This asymmetry becomes significant during some multiplications. Consider the case of an integer multiplication between two 4-bit two's complement numbers. Each integer operand may be expressed by a most-significant sign bit and three integer bits. The product can normally be expressed as a sign bit and six integer bits, or a total of (M+N-1) bits, where M and N represent the number of bits in the multiplier and multiplicand, respectively. For example, TABLE I illustrates a 4-bit-by-4-bit two's complement integer multiplication between -7 and -7:
TABLE I __________________________________________________________________________ Decimal Two's complement Binary representation of representation representation corresponding positive number __________________________________________________________________________ -7 1001 0 1 1 1 .times. -7 .times. 1001 .times. 0 1 1 1 +49 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 S S I I I I I I __________________________________________________________________________
where S represents the sign bits and I the integer bits. Since the sign bits are the same, the eighth bit may be truncated, and the product of -7 and -7 can be expressed with a sign bit and (4+4-2) integer bits using a 7-bit two's complement representation. Note that (M+N-1) bits are sufficient for all other combinations in the number system except for a multiplication between two operands which are each equal to their maximum negative values.
For this special case, known as the maximum negative squared case, (M+N-1) bits are insufficient to express the product. For example, in 4-bit-by-4-bit two's complement, if -8 is multiplied by -8, the product is equal to +64. TABLE II illustrates the maximum negative squared case for 4-bit-by-4-bit two's complement:
TABLE II __________________________________________________________________________ Decimal Two's complement Binary representation of representation representation corresponding positive number __________________________________________________________________________ -8 1000 1 0 0 0 .times. -8 .times. 1000 .times. 1 0 0 0 +64 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 S I I I I I I I __________________________________________________________________________
In the maximum negative squared case, the sign bit and the most-significant integer bits are not the same, indicating that the product cannot be represented in (M+N-1) bits. If the sign bit were to be truncated, the result in 7-bit two's complement is negative sixty-four, which is the worst (most-incorrect) result. In general, for the maximum negative squared case, the product of an M-bit multiplier and an N-bit multiplicand can only be represented in (M+N)-bit two's complement. Thus, the size of the arithmetic circuitry, data paths, and registers must be increased by one bit to precisely represent the product in the maximum negative squared case, increasing integrated circuit cost and power consumption.